1. Technical Field
The present invention relates to an improved data processing system. In particular, the present invention relates to optimizing software program in a compiler of a data processing system. Still more particularly, the present invention relates to optimizing software program in a compiler of a data processing system using inter-procedural strength reduction.
2. Description of Related Art
A compiler is a program that executes in a data processing system, which translates a high-level language program into a functionally equivalent low-level language program, such as machine language instructions. In the process of compilation, the compiler optimizes the source program by generating an explicit intermediate representation and performing code optimization.
Currently, well-known code optimization techniques, such as strength reduction, are used by many compilers to optimize code. Strength reduction includes reformulating certain costly computations in terms of less expensive ones. For example, by replacing certain repeated multiplications with repeated additions inside a loop containing array references may increase performance of loop execution. This increase in performance is due to reduction in total number of operations in the loop with the use of less costly operations. However, strength reduction is restricted to optimizing code of a single procedure, that is, intra-procedurally.
Another well known code optimization technique is introduced by Chauhan and Kennedy, which reduces a library procedure in strength by splitting the procedure based on the call arguments. The library procedure is split into two component procedures. An initialization part in which computations depend only on loop invariant arguments and can be moved outside the loop. Another part depends on loop index and remains inside the loop.
In addition to implementing the above well known techniques, most modern compilers are also designed to utilize multiple passes of the source program to collect information that can be used for code optimization, for example, a two pass inter-procedural analysis. A first pass is performed at compile time to collect summary information for each procedure compiled. A second pass is performed at link time and uses information collected in the first pass to compute a solution that improves structure of code produced by the compiler.
However, a need exists for a solution that takes the information collected in the two passes and analyzes it to select costly computations that are candidates for strength reduction across procedures in a source program.
Therefore, it would be advantageous to have an improved method and apparatus for a solution that pre-computes computation costs and reduces costly computations in strength inter-procedurally, that is, optimizing code in more than one procedure, such that performance of compiled code execution may be improved.